package com.example.linearSearch;

import java.util.Random;
// 用线性查找的方式找到第k大的数
public class LinearSearch {
    public static void main(String[] args) {
//        int[] arr = {7, 2, 8, 9, 3, 6, 1, 5, 4};
////        int num = recursiveLinearSearch(arr, 0, arr.length - 1, 9);
//        int num = iterativeLinearSearch(arr, 0, arr.length - 1, 9);
//        System.out.println(num);
        char c1 = '巉',c2 = '岩';
        System.out.println(c1 - c2);
    }
    // 使用递归的方法
    public static int recursiveLinearSearch(int[] arr, int left, int right, int k) {
        if (left == right) {
            return arr[left];
        }
        int index = partition(arr, left, right);
        int leftNum = index - left + 1;
        if (k < leftNum) {
            return recursiveLinearSearch(arr, left, index - 1, k);
        } else if (k > leftNum) {
            return recursiveLinearSearch(arr, index + 1, right, k - leftNum);
        } else {
            return arr[index];
        }
    }

    // 使用迭代的方法
    private static int iterativeLinearSearch(int[] arr, int left, int right, int k) {
        int l = left, r = right, index;
        while (l < r) {
            index = partition(arr, l, r);
            int leftNum = index - l + 1;
            if (k < leftNum) {
                r = index - 1;
            } else if (k > leftNum) {
                l = index + 1;
                k -= leftNum;
            } else {
                return arr[index];
            }
        }
        return arr[l];
    }


    // 随机产生一个下标，该下标左边的数都比其值大，其右边的数都比其值小
    private static int partition(int[] arr, int left, int right) {
        Random random = new Random();
        int ranIndex = random.nextInt(right - left + 1) + left;
        // 将ranIndex位置的数交换到left位置
        swap(arr, left, ranIndex);
        // 采用类似快速排序的方式，返回左右指针相遇时的坐标
        return likeQuickSort(arr, left, right);
    }

    private static int likeQuickSort(int[] arr, int left, int right) {
        int l = left, r = right, base = arr[left];
        while (l != r) {
            while (l < r && arr[r] <= base) {
                r--;
            }
            while (l < r && arr[l] >= base) {
                l++;
            }
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        arr[left] = arr[l];
        arr[r] = base;
        return l;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
